\documentclass[12pt]{article}
\usepackage{amsmath,amsthm}
\usepackage{times}
\usepackage{verbatim}

\newtheorem{defn}{Definition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}

\begin{document}

\section*{Kernel}
\paragraph{}
Immediately following Assignment 1, you will have to begin work on a kernel.
This will involve writing (among other things) assembly code for context
switching.

\section*{Miscellanea}
\paragraph{}
\begin{itemize}
\item The ARM MUL instruction does not load the result into a 64-bit result
register; rather, it gives you the low-order 32 bits.
\end{itemize}

\section*{Real-Time}
\paragraph{}
In a real-time system, timing is important - correctness is no longer
sufficient. Computations completed too early can be equally as disastrous as
those completed too late. Real-time embedded systems must provide guarantees
as to timing and reliability. Every algorithm you use must be constant-time.
(More accurately, any non-constant-time algorithms must be able to guarantee
reasonable bounds on input size.)

\subsection*{Aspects of Performance}
\begin{itemize}
\item throughput: not considered as a real-time programming problem, as this is
usually limited by available hardware
\item response time: you \textit{must} use the incoming data quickly enough
to receive more data!
\end{itemize}

\subsection*{Busy-Waiting}
\paragraph{}
\begin{verbatim}
#define FOREVER for(;;)
FOREVER {
  while (test) ;    // str, beq
  do_something;     // ld, str
}
\end{verbatim}

This executes a series of instructions:

\begin{verbatim}
str beq str beq ... beq ld str
\end{verbatim}

The worst-case scenario is if the test condition (ready bit, etc.) switches
immediately after the \texttt{str} operation.

\paragraph{}
Of course, we can get optimal performance by simply waiting for the ``right''
amount of time:

\begin{verbatim}
     NOP
LBL: NOP
     ...
     NOP
     ld
     str
     br LBL
\end{verbatim}

We tune the \texttt{NOP} sequence to the frequency at which the desired state
bit is set. Here we sacrifice an incredible amount of flexibility for raw
performance.

\paragraph{}
The problem with the infinite loop above is simple: it only does one thing
at once! If we want to do multiple things (say, in the context of a certain
assignment\ldots), we need something called a polling loop.

\subsection*{Polling Loops}
\paragraph{}
A polling loop is a busy-wait in which multiple conditions are tested.
\begin{verbatim}
FOREVER {
  if (test1) action1;
  if (test2) action2;   // clock++;
  ...
  if (testN) actionN;
}
\end{verbatim}

In the worst case, \texttt{test1} becomes true immediately after it is tested
and all other tests are true.

\paragraph{}
Problems arise when the actions are interdependent. For instance, suppose
\texttt{test1} determines if I/O is to be done, but \texttt{action2}
increments and updates the displayed clock. We can reduce some of the
programming complexity by placing everything (well, everything important) at
global scope.

\paragraph{}
For timing purposes, the ARM processor offers a 40-bit clock that ticks once
per clock cycle. It is important to establish timing guarantees - once many
conditions and their corresponding actions are placed in the polling loop,
the time per iteration may exceed the polling interval necessary to receive
all sensor and device information. On Monday, we will see various techniques
for handling this problem.

\end{document}
